In many computer graphics applications, an image displayed on a two-dimensional display screen is generated by transforming another image, called a source image. For example, the source image may be texture mapped to a three-dimensional object which is projected onto a two-dimensional plane defined by the display. Another application includes special effects in motion video or animation in which a source image is deformed to create a desired image.
The source image can be represented by a rectangular grid of samples of a continuous 2-D function f(x,y). Each sample is the value of the continuous function at a given sample point or pixel, with each pixel representing a point of the image, including the color of the image at that point. An ideal procedure for scaling the image, i.e., an image represented as discrete pixel locations along fixed scan lines in a rectangular array of scan lines, involves reconstructing the original continuous function of the source image from the sampled data and then deforming the continuous image. A low pass filter is applied to eliminate frequencies in the destination image above a Nyquist frequency. The Nyquist frequency determines the lowest sampling rate possible to preserve details in the image and is equal to twice the frequency of the highest frequency component in a source signal. The low pass filter is used since any frequency component that is higher than half the sampling rate will be sampled incorrectly and will be aliased to a lower frequency. After applying the filter, sampling is performed on the continuous function of the deformed image using a different sampling resolution to produce a destination image. According to sampling theory, the sinc function f(x,y)=[sin(.pi.x)sin(.pi.y)]/.pi..sup.2 x, is ideal for reconstructing a two-dimensional image. Sampling would determine the color value of each point in the destination to create the final destination image. The entire process of reconstructing, deforming, filtering and sampling is known as resampling.
However, in practice, the ideal process as outlined above is impractical, primarily because an ideal reconstruction filter cannot be implemented practically. For instance, since the sinc function is nonzero on points arbitrarily far from the origin, performing computations on all points is impractical. Therefore, a finite reconstruction filter is used, such as bilinear and bicubic filters are often used for filtering the signal representing a source image. In addition, an actual continuous image cannot be represented in a computer environment and a continuous image cannot be easily distorted.
One way to simulate the ideal process includes applying a transformation to regularly spaced pixels from a source image and then applying a low pass filter to the transformed image. However, after the transformation is applied, the transformed image may no longer include regularly spaced points and applying a low pass filter to the irregularly spaced points is difficult to perform.
In conventional systems, scaling down may be performed using mip-mapping techniques. In mip-mapping, although a standard shape of a square is used in filtering, the area of the filter may vary. A source image is successively averaged down to a lower resolution. Each image is half the resolution of the previous image, i.e., half the linear dimension and a quarter the number of samples of its previous image. Using bilinear interpolation, an intensity is determined for values of each pixel as it is scaled down. Linear interpolation between levels of filtering further smooths the values. However, in motion video applications, mip-mapping may produce undesired artifacts.
Standard box filtering may also be used for mapping an image. A rectangular box corresponding to the approximate shape of the destination pixel may be used to compute a filtered pattern value for the pixel by summing all of the values in the source image included in the rectangle. Each destination pixel has a value that is a weighted average of an area of source pixels. However, if the transformed pixel is not approximately an aligned rectangle, then undesired artifacts may result in the destination image.
The problem of undesired artifacts may be particularly troublesome when an image is non-uniformly scaled, i.e., is subject to an arbitrary deformation. These artifacts arise particularly when applying special effects to an image which involves altering at least one portion of the image differently from other portions of the image. Two examples of a non-uniform special effect scaling include sphere and ripple. When applying a ripple effect, the resulting image includes a ripple pattern, such as one resulting from throwing a stone in a lake. Applying the sphere effect creates an enlarged lateral portion of a sphere, i.e., a "bulge", while maintaining the surrounding image in the sphere.
A need exists for a system or process for transforming a source image to a destination image which approximates the ideal resampling process and eliminates the artifacts caused by conventional filtering methods used with non-uniform scaling applications.